package com.algorithm.ch1.cjm.tree;

import com.algorithm.ch1.cjm.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 验证二叉搜索树
 * <p>
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 假设一个二叉搜索树具有如下特征：
 * <p>
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * 示例 1:
 * <p>
 * 输入:
 * 2
 * / \
 * 1   3
 * 输出: true
 * 示例 2:
 * <p>
 * 输入:
 * 5
 * / \
 * 1   4
 * / \
 * 3   6
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 * 根节点的值为 5 ，但是其右子节点值为 4
 */
public class IsValidBST {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(0);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        root.left = node1;
        node1.left = node2;
        node2.left = node3;
        root.right = node4;
        node4.right = node5;
        node5.right = node6;

//        IsValidBST ma = new IsValidBST();
//        boolean flag = ma.isValidBST1(root);

        ArrayList<Integer> res = new ArrayList<>();
        TreeNode.inorderTraversal(root, res);

        System.out.println(Arrays.toString(res.toArray()));
    }

    /**
     * 第一版
     * T(n) = n + n + n;
     * f(n) = n;
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {

        if(root == null){
            return true;
        }

        //查询右节点最小的点
        if(root.right != null){

            TreeNode cur = root.right.left;
            while (cur != null) {
                //右边做小的点小于根节点
                if(root.val >= cur.val){
                    return false;
                }

                cur = cur.left;
            }
        }

        //查询左节点最大的点
        if(root.left != null){

            TreeNode cur1 = root.left.right;
            while (cur1 != null){

                //左边最大的点大于根节点
                if(root.val <= cur1.val){
                    return false;
                }

                cur1 = cur1.right;
            }
        }

        boolean flag = isValidBST(root.left) && isValidBST(root.right);

        if(!flag){
            return false;
        }

        int rootVal = root.val;

        if(root.left != null && root.left.val >= rootVal){
            return false;
        }

        if(root.right != null && root.right.val <= rootVal){
            return false;
        }

        return true;
    }


    /**
     * 前一个节点
     */
    private TreeNode pre;


    /**
     * leetcode最优解
     *
     * 厉害，厉害，
     * @param root
     * @return
     */
    public boolean isValidBST1(TreeNode root){

        if(root == null){
            return true;
        }
        boolean f = isValidBST1(root.left);

        boolean f2 = pre == null || pre.val < root.val;

        pre = root;

        boolean f1 = isValidBST1(root.right);

        return f && f2 && f1;
    }


}
